import math

POINTS = [(1.83, 3.43), (1.17, 3.37), (1.23, 2.2), (2.67, 2.47), (2.67, 3.73), (2.43, 3.37), (2.23, 2.7), (1.97, 2.3),
          (1.53, 2.73), (1.97, 2.9), (1.97, 4.1), (1.33, 4.1), (1.63, 3.93), (1.1, 3.8), (1.43, 3.77), (1.6, 3.17),
          (1.2, 3.13), (0.83, 3.13), (0.9, 2.33), (1.0, 2.83), (4.27, 2.33), (3.93, 1.8), (4.03, 1.07), (4.73, 1.1),
          (4.8, 2.33), (4.27, 2.63), (3.6, 2.7), (3.67, 3.23), (3.1, 2.9), (2.83, 3.1), (3.6, 1.57), (3.47, 1.93),
          (4.07, 2.2), (3.83, 2.43), (4.67, 1.5), (4.3, 1.8), (4.63, 2.1), (4.73, 2.9), (4.63, 3.27), (1.4, 1.37),
          (1.77, 0.6), (2.63, 0.77), (2.67, 1.03), (2.33, 1.4), (1.77, 1.4), (1.77, 1.0), (2.13, 1.03), (1.2, 1.07),
          (1.2, 0.5), (1.67, 0.5), (1.67, 0.5), (2.4, 0.47), (3.13, 0.5), (3.07, 1.4), (2.47, 1.4), (2.33, 0.77),
          (1.6, 0.87), (1.53, 1.07), (1.53, 0.67), (2.23, 0.67), (2.3, 1.23)]


def clustered_points(min_pt, max_pt, k):
    import random
    clustered_point = []
    for i in range(k):
        clustered_point.append(
            (random.randint(int(min_pt[0]), int(max_pt[0] + 1)), random.randint(int(min_pt[1]), int(max_pt[1] + 1))))
    # print(clustered_point)
    return clustered_point


def distance(pt1, pt2):
    return math.sqrt(math.pow(pt2[0] - pt1[0], 2) + math.pow(pt2[1] - pt1[1], 2))


def plot_points(cps, data):
    from matplotlib import pyplot as plt
    for k, points in data.items():
        plt.scatter([x for x, _ in points], [y for _, y in points])
    for cpx, cpy in cps:
        plt.scatter([cpx], [cpy])
    plt.show()


def get_new_center_points(data, cps):
    new_clustered_points = {}
    for cp in cps:
        new_clustered_points[cp] = []

    for x, y in data:
        min_distance = 0
        clustered_pt = None
        for cpx, cpy in cps:
            dis = distance((x, y), (cpx, cpy))
            if clustered_pt is None:
                min_distance = dis
                clustered_pt = (cpx, cpy)
                continue
            if min_distance > dis:
                min_distance = dis
                clustered_pt = (cpx, cpy)
        new_clustered_points[clustered_pt].append((x, y))

    new_center_points = []

    for cps, points in new_clustered_points.items():
        newx = sum([x for x, _ in points]) / len(points)
        newy = sum([y for _, y in points]) / len(points)
        new_center_points.append((newx, newy))
    return new_center_points, new_clustered_points


def k_mean(data, k):
    min_x, min_y, max_x, max_y = data[0][0], data[0][1], data[1][0], data[1][1]
    for x, y in data:
        if min_x > x:
            min_x = x
        if max_x < x:
            max_x = x

        if min_y > y:
            min_y = y
        if max_y < y:
            max_y = y

    # 随机生成k个轴心点
    cps = clustered_points((min_x, min_y), (max_x, max_y), k)

    while True:
        for i in range(len(cps)):
            new_center_points, new_clustered_points = get_new_center_points(data, cps)
            dis = distance(new_center_points[i], cps[i])
            print(cps)
            print(new_center_points)
            if dis > 0:
                cps = new_center_points
                continue
            else:
                return new_center_points, new_clustered_points


cps, points =k_mean(POINTS, 3)
plot_points(cps, points)
# print(points)
